package Explorer.Exp2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Graph {
	
	private HashMap<String,Noeud> map;
	
	public Graph()
	{
		map = new HashMap<String, Noeud>();
	}
	
	public void addNoeud(String id)
	{
		map.put(id, new Noeud(id));
	}
	public void addNoeud(Noeud n)
	{
		map.put(n.getName(), n);
	}
	public boolean isPresent(String id)
	{
		return map.containsKey(id);
	}
	
	public Chemin pathTo(String from, String to)
	{
		if(isPresent(from) && isPresent(to))
		{
			return this.pathDij(from, to);
		}
		else
			return null;
	}
	
	private Chemin pathDij(String from, String to)
	{
		ArrayList<Chemin> list = new ArrayList<Chemin>();
		
		Noeud depart = map.get(from);
		Noeud arrive = map.get(to);
		
		boolean find = false;
		
		list.add(new Chemin(depart.getName()));
		
		Chemin bestChemin = list.get(0);
		Arete bestArete = depart.getAretes().get(0);
		
		
		while(!find)
		{
			bestChemin = list.get(0);
			int i= 1;
			ArrayList<Chemin>del = new ArrayList<Chemin>();
			
			for(Chemin c : list)
			{
				if(c.completementVisite(map.get(c.getDernierNoeud())))
					del.add(c);
				else 
					bestChemin = c; 
			}
			
			for(Chemin c : del)
				list.remove(c);
			int poids; 
			Noeud n = map.get(bestChemin.getDernierNoeud());
			boolean init = false;
			bestArete= null;
			i =0;
			while(!init)
			{
				bestArete = n.getAretes().get(i);
				if(!bestChemin.isNodeVisited(bestArete.getArrive().getName()))
				 init = true;
				else
					i++;
			}
				
			poids = bestArete.getPoids()+bestChemin.getPoids();
			
			for(Chemin c : list)
			{
				n = map.get(c.getDernierNoeud());
				for(Arete a : n.getAretes())
				{
					if((a.getPoids()+c.getPoids() < poids) && 
													!(c.isNodeVisited(a.getArrive().getName())))
					{
						
						poids = a.getPoids()+c.getPoids();
						bestChemin = c;
						bestArete = a;
					}
				}
			}
			
			Chemin tmp = bestChemin;
			
			if(tmp.completementVisite(map.get(tmp.getDernierNoeud())))
				list.remove(tmp);
			
			bestChemin = bestChemin.newFrom(bestArete.getArrive().getName());
			bestChemin.addNoeud(bestArete.getArrive().getName(), bestArete.getPoids());
			
			list.add(bestChemin);
			
			find = (bestArete.getArrive() == arrive);
			
		}
	return bestChemin;
		
	}
	
	public Noeud getNoeud(String id)
	{
		if(map.containsKey(id))
			return map.get(id);
			else 
				return null;
	}
	
	public Map<String, Noeud> getMap()
	{
		return map;
	}

}
